package com.zdp.leetcodeMiddle;

public class 数组中的最长山脉 {
    /*
    * 给出一个整数数组，返回最长“山脉”的长度。 山脉是满足一定条件的 连续子数组
    * 条件：  ====> 可以看出 “山脉” 就是 两边低 中间高 不相等
    *  B.length >=3
    *  存在 0<i<B.length-1 使得B[0]<B[1]<....B[i-1]<B[i]>B[i+1]>...>B[B.length-1]
    * B可以是A的任意子数组，也包括整个数组A
    *
    * 限制条件：
    * 0<=A.length <=10000
    * 0<=A[i] <=10000
    * */

    /*
    * 解题思路：
    * 一般思路是 枚举一个j，然后从j开始，向两边扩张找到连续的子数组 ----> 时间复杂度为O(n*n)
    * 所以 想办法优化， 因为 从山脚到山顶的单调递增，山顶到右侧山脚是单调递减
    * 所以可以使用两个数组，一个用来记录左侧山脚到山顶的连续子数组长度
    * j作为山顶，j的连续子数组的长度可以在j-1的基础上得到，
    * 同理，另一个数组用来记录山顶到右侧山脚的长度
    * j 作为山顶，j到右侧山脚的长度可以在j+1的基础上得到
    *
    * */
    public int longestMountain(int[] arr) {
        int[] left = new int[arr.length]; //left[i] : 表示 i的左侧（不包含i） 有几个连续的数比i小
        int[] right = new int[arr.length]; //right[i] : 表示 i的右侧（不包含i），有几个连续的数比i大
        int max = 0;
        // left[] 中 不被依赖的位置 0位置，0位置左侧没有数，所以为0
        for(int i=1;i<arr.length;i++){
            left[i] = arr[i]>arr[i-1]?left[i-1]+1:0;
        }
        //right[] 中，不被以来的位置 length-1位置，length-1位置右侧没有数，所以为0
        for(int i=arr.length-2;i>=0;i--){
            right[i] = arr[i]>arr[i+1]?right[i+1]+1:0;
        }
        for(int i=0;i<arr.length;i++){
            if(left[i]!=0&&right[i]!=0)
                max = Math.max(max,(left[i]+right[i]+1));
        }
        return max;
    }
}
